二叉树的性质：
            -节点的左子树只包含小于当前节点的数。
            -节点的右子树只包含大于当前节点的数。
            -所有左子树和右子树自身必须也是二叉搜索树。
            -中序遍历的序列是有序的
class Solution {
    
    /*
                         思路1：递归
         5
      2     7    
    1   3  6  8  对于这棵二叉搜索树，我们容易知道：
        如果某个节点是他父亲的右儿子，那么节点所在的子树的最小值为父亲的值
        反之，这个节点的最大值就是它父亲的值
    */
    public boolean isValidBST(TreeNode root) {
        return dfs(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean dfs(TreeNode root,long minVal,long maxVal){
        if( root==null )
            return true;
        if( root.val<=minVal || root.val>=maxVal )
            return false;
        return dfs(root.left,minVal,root.val) && dfs(root.right,root.val,maxVal);
    }
}

class Solution {
    /*
        二叉搜索树「中序遍历」得到的值构成的序列一定是升序的
    */
    public boolean isValidBST(TreeNode root) {
        long pre = Long.MIN_VALUE;
        if( root==null  )
           return false;
        Deque<TreeNode> st = new LinkedList<>();
        while( !st.isEmpty() || root!=null){
            while( root!=null ){  // 向左子树遍历
                st.push(root);
                root = root.left;
            }
            if( !st.isEmpty() ){
                TreeNode tmp = st.pop();
                // System.out.print(tmp.val+" ");  中序遍历的节点、、、、、
                if( pre>=tmp.val )
                    return false;
                pre = tmp.val;
                root = tmp.right;
            }
        }
        return true;
    }
}